package name.huzhenbo.java.algorithm.sort;

public class CountingSorter implements Sorter{
    public int[] go(int[] input) {
        int[] counter = new int[max(input) + 1];
        for(int i: input){
            counter[i]++;
        }

        int previous = 0;
        for(int i = 1; i < counter.length; i++){
            if(counter[i] == 0) continue;
            counter[i] += counter[previous];
            previous = i;
        }

        int[] result = new int[input.length];
        previous = 0;
        for(int i = 0; i < counter.length; i++){
            if(counter[i] != 0){
                for(int j = previous; j < counter[i]; j++) {
                    result[j] = i;
                }
                previous = counter[i];
            }
        }
        return result;
    }

    private int max(int[] input) {
        int max = Integer.MIN_VALUE;
        for(int i: input){
            if(i > max) max = i;
        }
        return max;
    }
}
